package LeetCode;

import java.util.LinkedList;
import java.util.List;

public class LC_321_CreateMaximumNumber {

    public static void main(String[] args) {

    }

    static class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            List<Integer> list = new LinkedList<>();
            int[] ans = new int[k];
            for (int i = 0; i <= k; i++) {
                if (i <= nums1.length && k - i <= nums2.length) {
                    int[] res = merge(maxNum(nums1, i), maxNum(nums2, k - i), k);
                    if (larger(res, ans, 0, 0)) ans = res;
                }
            }
            return ans;
        }

        boolean larger(int[] res, int[] ans, int r, int a) {
            while (r < res.length && a < ans.length && res[r] == ans[a]) {
                r++;
                a++;
            }
            return a == ans.length || (r < res.length && res[r] > ans[a]);
        }

        int[] maxNum(int[] nums, int k) {
            int[] res = new int[k];
            int j = 0, n = nums.length;
            for (int i = 0; i < nums.length; i++) {
                while (n - i + j > k && j > 0 && res[j - 1] < nums[i]) j--;
                if (j < k) res[j++] = nums[i];
            }
            return res;
        }

        int[] merge(int[] nums1, int[] nums2, int k) {
            int[] res = new int[k];
            int i = 0, j = 0;
            for (int index = 0; index < k; index++)
                res[index] = larger(nums1, nums2, i, j) ? nums1[i++] : nums2[j++];
            return res;
        }

    }
}